De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  gastenboek |  wie is wie? |  verhalen |  contact

HOME

samengevat

vragen bekijken

een vraag stellen

hulpjes

zoeken

FAQ

links

twitter

boeken

help

inloggen

colofon

Reageren...

Re: Wortel zonder breuk onder het wortelteken

I.v.m. een opdracht was ik bezig om een discrete logaritme te vinden van een getal y (de oplossing van f(x)=y) waarbij f(x)=2^x mod p, en p een enorm lang priemgetal is.

Nou is dit voor bijna alle waarden van y zeer moeilijk te vinden, maar zou dit voor y=p-1 heel makkelijk te bepalen moeten zijn. Ik kom er zelf echter niet uit. Brute force rekenen mag dus niet de oplossing zijn (daarnaast bestaat p uit 35 cijfers, dus het is vrijwel ondoenelijk). Er moet dus een makkelijke methode zijn waarmee het eenvoudig te bepalen is. Ik heb de oplossing geprobeerd te zoeken in de stelling dat 2^(p-1) mod p = 1 (dit geldt voor alle priemgetallen), maar ik kom er daar ook niet mee uit.

Antwoord

p is oneven, dus p-1 is even. Bekijk a=2^(p-1)/2, er geldt dan a²=1 en dus a=1 of a=-1 (mod p). Er geldt a=-1.

Gebruik dit formulier alleen om te reageren op de inhoud van de vraag en/of het antwoord hierboven. Voor het stellen van nieuwe vragen kan je gebruik maken van een vraag stellen in het menu aan de linker kant. Alvast bedankt!

Reactie:
	Klik eerst in het tekstvlak voordat je deze knopjes en tekens gebruikt. Pas op: onderstaande knopjes en speciale karakters werken niet bij ALLE browsers! áâæàåãäßçéêèëíîìïñóôòøõöúûùüýÿ½¼¾€£®© $\forall$$\exists$$\neg$$\wedge$$\vee$$\Leftrightarrow$$\Leftarrow$$\Rightarrow$$\emptyset$$\cap$$\cup$$\supset$$\supseteq$$\not\subset$$\subset$$\subseteq$$\in$$\notin$ $\sim$$\equiv$$\ne$$\pm$$\times$$\div$$\otimes$$\oplus$$\pi$$\leftarrow$$\uparrow$$\to$$\downarrow$ $\sqrt{}$$\sum$$\prod$$\infty$$\smallint$$\Delta$$\nabla$$\partial$$\angle$$\bot$$\cong$$\widehat p$ $\alpha$$\beta$$\gamma$$\delta$$\varepsilon$$\phi$$\theta$$\lambda$$\mu$$\rho$$\sigma$$\tau$$\omega$$\chi$$\Gamma$$\vartheta$$\Lambda$$\Omega$$\Psi$$\zeta$ $\mathbf{N}$ $\mathbf{Z}$ $\mathbf{Q}$ $\mathbf{R}$ $\mathbf{C}$
Categorie:	Rekenen
Ik ben:	-------------- Maak een keuze --------------- Leerling onderbouw vmbo-havo-vwo Leerling bovenbouw vmbo Leerling bovenbouw havo-vwo Leerling mbo Student hbo Student universiteit 1ste graad ASO-TSO-BSO Overige TSO-BSO 2de graad ASO 3de graad ASO Student Hoger Onderwijs België Student universiteit België Cursist vavo Docent Ouder Iets anders Beantwoorder
Naam:
Emailadres:
Datum:	20-5-2024